package io.github.consoles.dsa;

import java.util.Iterator;

/**
 * Created by yiihua-013 on 17/3/31.
 */
public class ArrayDequeue<Item> implements Iterable<Item> {

    private static final int DEFAULT_CAPACITY = 2;

    private Item[] data;
    private int    size;

    public ArrayDequeue(int initCap) {
        data = (Item[]) new Object[initCap];
    }

    public ArrayDequeue() {
        this(DEFAULT_CAPACITY);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void pushLeft(Item item) {

        if (size == data.length) resize(2 * size);

        // 从前向后赋值是错误的
//        for (int i = 1; i < size + 1; i++) {
//            data[i] = data[i - 1];
//        }

        for (int i = size; i > 0; i--) {
            data[i] = data[i - 1];
        }

        data[0] = item;
        size++;
    }

    public void pushRight(Item item) {
        if (size == data.length) resize(2 * size);
        data[size++] = item;
    }

    public Item popLeft() {

        if (isEmpty()) throw new RuntimeException("queue is empty!");

        Item item = data[0];

        for (int i = 0; i < size - 1; i++) data[i] = data[i + 1];
        size--;
        if (size == data.length / 4) resize(data.length / 2);

        return item;
    }

    public Item popRight() {
        if (isEmpty()) throw new RuntimeException("queue is empty!");

        Item item = data[size - 1];
        data[--size] = null;
        if (size == data.length / 4) resize(data.length / 2);
        return item;
    }

    private void resize(int cap) {
        Item[] tmp = (Item[]) new Object[cap];
        for (int i = 0; i < size; i++) {
            tmp[i] = data[i];
        }
        data = tmp;
    }

    private class DequeIterator implements Iterator<Item> {

        private int currentIndex = 0;

        @Override
        public boolean hasNext() {
            return currentIndex != size;
        }

        @Override
        public Item next() {
            return data[currentIndex++];
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new DequeIterator();
    }
}
